import sys
sys.path.append(r'C:\Users\lenovo\Desktop\python-data-structure-cn-master\pyhon实现相关算法和数据结构\queue')
from graph import Graph
from Queue import Queue


# 根据单词创建图
def buildGraph(wordFile):   # wordFile里面存了单词
    d = {}  # 开始用来存储那个桶
    g = Graph() # 创建图
    wfile = open(wordFile,'r')

    # 创建桶
    for line in wfile:
        word = line[:-1]
        for i in range(len(word)):
            bucket = word[:i] + '_' + word[i+1:]
            if bucket in d:
                d[bucket].append(word)
            else:
                d[bucket] = [word]

    # 将每个桶中的单词加入图
    for bucket in d.keys():
        for word1 in d[bucket]:
            for word2 in d[bucket]:
                if word1 != word2:
                    g.addEdge(word1,word2)

    return g

# 现在已经创建了含有单词的图，用广度优先搜索进行搜索(BFS)
# 颜色白色表示没有加入队列，为灰色表示加入队列但没进行邻接点处理，为黑色表示加入队列后处理过邻接点并删除的。
# 我们找一个节点的邻接点时判断邻接点颜色，只添加白色进去
def bgs(g,start):   # bfs算法
    start.setColor('gray')
    start.setDistance(0)    # 起始点距离起始点距离为0
    start.setPred(None)
    verQueue = Queue()  # 队列
    verQueue.enqueue(start)

    while (verQueue.size() > 0):
        currentVert = verQueue.dequeue()    # 队列中取出一个节点
        for nbr in currentVert.getConnections():    # currentVert.getConnections()返回的就是一个列表
            if nbr.getColor() == 'white':   # 该节点没有加过队列
                nbr.setColor('gray')
                nbr.setDistance(currentVert.getDistance() + 1)  # 距离加1
                nbr.setPred(currentVert)
                verQueue.enqueue(nbr)
        currentVert.setColor('black')

# 回溯函数，输入起始点，得到起始点到终点的路径
def traverse(end):
    y = end
    while(y.getPred()):
        y = y.getPred()
        print(y.getId())
    print(y.getId)  # 其实打印的是最后一个终点,修改成功

if __name__ == '__main__':
    wordGraph = buildGraph('word.txt')  # 创建单词图
    bgs(wordGraph,start= wordGraph.getVertex('FOOL')) # Fool为起点对图进行了广度优先搜索，信息保存在距离和前驱中
    print(wordGraph.getVertex('SAGE').getDistance())
    traverse(end= wordGraph.getVertex('SAGE'))
